/***
 * Implement a BigInteger modular exponentiation routine 
 * by repeatedly squaring a running total
 * 
 */

package timingAttack;

import java.math.BigInteger;

/***
 * Store, time, and calculate the result of one or more iterations of a 
 * square & multiply modular exponentiation routine
 * 
 * @author Vincent
 *
 */
public class ModExp 
{
	// impose a delay for one-bits to try to coax a result
	static int delayMillis = 0;
	
	// Member variables
	public BigInteger value;	// This is the value after the specified bits
	public long time;			// This is how long the requested iterations took
	
	// Simple constructor
	public ModExp( BigInteger value, long time )
	{
		this.value = value;
		this.time = time;
	}
	
	/***
	 * Carry out and time iterations of a square and multiply modular 
	 * exponentiation routine
	 * @param currentValue	current value after previous iterations
	 * @param modulus		
	 * @param message
	 * @param bits			boolean array of bits--true for 1
	 */
	public ModExp( BigInteger currentValue, BigInteger modulus, BigInteger message, boolean [] bits )
	{
		System.gc();
		
		long start, end;
		
		end = System.nanoTime();
        start = System.nanoTime();
		for( int i = 0; i < bits.length; i++ )
		{
			if( !bits[i] )
			{
				currentValue = currentValue.multiply(currentValue);
				if(currentValue.compareTo(modulus) > 0)
					currentValue = currentValue.mod(modulus);
				// currentValue = currentValue.multiply(currentValue).mod(modulus);
			}
			else 
			{
				currentValue = currentValue.multiply(currentValue);
				if(currentValue.compareTo(modulus) > 0)
					currentValue = currentValue.mod(modulus);
				currentValue = currentValue.multiply(message);
				if(currentValue.compareTo(modulus) > 0)
					currentValue = currentValue.mod(modulus);
				// currentValue = currentValue.multiply(currentValue).mod(modulus);
				// currentValue = currentValue.multiply(message).mod(modulus);

				// Induce the delay
				if(delayMillis > 0)
					try 
					{
						Thread.sleep(delayMillis);
					} 
					catch (InterruptedException e) 
					{
						e.printStackTrace();
						System.exit(-1);
					}
			}
		}
        end = System.nanoTime();

		this.time = (end - start);
		this.value = currentValue;
	}
	
	/***
	 * Carry out and time iterations of a square and multiply modular 
	 * exponentiation routine with an artificial delay for 1-bits in
	 * the exponent
	 * @param currentValue	current value after previous iterations
	 * @param modulus		
	 * @param message
	 * @param bits			boolean array of bits--true for 1
	 */
	public ModExp( BigInteger currentValue, BigInteger modulus, BigInteger message, boolean [] bits, int delayMillis )
	{
		int old = ModExp.delayMillis;
		ModExp.delayMillis = delayMillis;

		ModExp m = new ModExp( currentValue, modulus, message, bits );
		this.value = m.value;
		this.time = m.time;
		
		ModExp.delayMillis = old;
	}
	
	/***
	 * Carry out and time modular exponentiation iterations
	 * with a BigInteger exponent and with an artificial delay for 1-bits in
	 * the exponent
	 * 
	 * @param currentValue	current value after previous iterations
	 * @param modulus		
	 * @param message
	 * @param exponent
	 * @param delayMillis	imposed delay for 1-bits in exponent		
	 */
	public ModExp( BigInteger currentValue, BigInteger modulus, BigInteger message, BigInteger exponent, int delayMillis )
	{
		boolean [] bits = new boolean[exponent.bitLength()];

		// bitLength() returns values from 1...bitLength()
		// testBit(i) accepts values for i from 0 to bitLength()-1
		for( int i = 0; i < bits.length; i++ )
		{
			bits[i] = exponent.testBit(bits.length-i-1);
		}
		
		ModExp m = new ModExp(currentValue, modulus, message, bits, delayMillis);
		
		this.value = m.value;
		this.time = m.time;
	}

	/***
	 * Carry out and time modular exponentiation iterations
	 * with a BigInteger exponent
	 * 
	 * @param currentValue	current value after previous iterations
	 * @param modulus		
	 * @param message
	 * @param exponent		
	 */
	public ModExp( BigInteger currentValue, BigInteger modulus, BigInteger message, BigInteger exponent )
	{
		this(currentValue, modulus, message, exponent, 0 );
	}

	/***
	 * Carry out and time a full modular exponentiation 
	 * with a BigInteger exponent
	 * 
	 * @param modulus		
	 * @param message
	 * @param exponent		
	 */
	public ModExp( BigInteger modulus, BigInteger message, BigInteger exponent )
	{
		this(BigInteger.ONE, modulus, message, exponent);
	}
	
	
	/***
	 * Carry out and time a full modular exponentiation 
	 * with a BigInteger exponent and with an artificial
	 * delay for 1-bits in the exponent
	 * 
	 * @param modulus		
	 * @param message
	 * @param exponent		
	 */
	public ModExp( BigInteger modulus, BigInteger message, BigInteger exponent, int delayMillis )
	{
		this(BigInteger.ONE, modulus, message, exponent, delayMillis);
	}
	
	/***
	 * Static method for modular exponentiation via repeated squaring
	 * 
	 * @param msg the number to square
	 * @param exp the exponent
	 * @param n the modulus
	 * @return msg^exp mod n
	 */
	static BigInteger modExp(BigInteger msg, BigInteger exp, BigInteger n)
	{
		ModExp m = new ModExp(n, msg, exp);
		return m.value;
	}
	
	/***
	 * Wrapper method that uses the static BigInteger
	 * modular exponentiation routine on longs
	 * 
	 * @param msg the number to square
	 * @param exp the exponent
	 * @param n the modulus
	 * @return msg^exp mod n
	 */
	static long modExp( long msg, long exp, long n )
	{
		return modExp(BigInteger.valueOf(msg), 
				 BigInteger.valueOf(exp), 
				 BigInteger.valueOf(n)).longValue();
	}

}
